#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
	int a,b;
	friend bool operator <(node A,node B)
	{
		return A.a<B.a;
	}
};
priority_queue<node>pqe;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		while(!pqe.empty()) pqe.pop();
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i = 0;i<n;i++)
		{
			node tmp;
			scanf("%d %d",&tmp.a,&tmp.b);
			pqe.push(tmp);
		}
		int ans = 0;
		while(!pqe.empty()&&m!=0)
		{
			m--;
			node tmp = pqe.top();
			pqe.pop();
			ans = ans+tmp.a;
			tmp.a = max(0,tmp.a-tmp.b);
			if(tmp.a!=0) pqe.push(tmp);
		}
		printf("%d\n",ans);
	}
}
